package fireway;

/**
 * 划分
 * 2018年 07月 22日 星期日
 *
 * @author fireway
 */
public class ArrayPartition {
    private long mLArray[];

    private int mSize;

    public ArrayPartition(int initialCapacity) {
        mLArray = new long[initialCapacity];
        mSize = 0;
    }

    public void insert(long e) {
        mLArray[mSize++] = e;
    }

    public void display() {
        System.out.print("[");
        for (int i = 0; i < mSize; i++) {
            System.out.print(mLArray[i]);
            if (i != mSize - 1) {
                System.out.print(", ");
            }
        }
        System.out.print("]\n");
    }

    public int partitioning(int left, int right, long pivot) {
        int leftPointer = left - 1;
        int rightPointer = right + 1;

        while (true) {
            while (leftPointer < right && mLArray[++leftPointer] < pivot) {}
            while (rightPointer > left && mLArray[--rightPointer] > pivot) {}

            if (leftPointer >= rightPointer) {
                break;
            } else {
                swap(leftPointer, rightPointer);
            }
        }

        return leftPointer;
    }

    private void swap(int left, int right) {
        long temp = mLArray[left];
        mLArray[left] = mLArray[right];
        mLArray[right] = temp;
    }
}
